use std::{cell::RefCell, fmt, rc::Rc};

// 1. 栈
#[derive(Debug)]
pub struct Stack<T> {
    v: Vec<T>,
}

impl<T> Stack<T> {
    pub fn bulid() -> Self {
        Stack { v: Vec::new() }
    }
    fn stack_emtpy(&self) -> bool {
        self.v.is_empty()
    }
    pub fn push(&mut self, x: T) {
        self.v.push(x);
    }
    pub fn pop(&mut self) {
        if self.stack_emtpy() {
            panic!("underflow");
        } else {
            self.v.pop();
        }
    }
}

// 2. 队列
#[derive(Debug)]
pub struct Queue<T> {
    v: Vec<T>,
}

impl<T> Queue<T> {
    pub fn build() -> Self {
        Queue { v: Vec::new() }
    }
    pub fn en_queue(&mut self, x: T) {
        self.v.push(x);
    }
    pub fn de_queue(&mut self) {
        self.v.remove(0);
    }
}

// 3. 链表
#[derive(Clone)]
pub struct DoubleLinkedList<T: PartialEq + Copy + fmt::Display> {
    key: T,
    prev: Option<Rc<RefCell<DoubleLinkedList<T>>>>,
    next: Option<Rc<RefCell<DoubleLinkedList<T>>>>,
}

impl<T: PartialEq + Copy + fmt::Display> DoubleLinkedList<T> {
    // 构建
    pub fn build(v: T) -> Self {
        DoubleLinkedList {
            key: v,
            prev: None,
            next: None,
        }
    }
}
// 格式化打印
impl<T: PartialEq + Copy + fmt::Display> fmt::Display for DoubleLinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{} ---> ", self.key)
    }
}

pub struct Head<T: PartialEq + Copy + fmt::Display> {
    head: Option<Rc<RefCell<DoubleLinkedList<T>>>>,
}
// 格式化打印
impl<T: PartialEq + Copy + fmt::Display> fmt::Display for Head<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut node = self.head.clone();
        while let Some(l) = node.as_ref() {
            print!("{}", Rc::clone(&l).as_ref().borrow());
            node = Rc::clone(&l).as_ref().borrow().next.clone();
        }
        write!(f, "Over")
    }
}

impl<T: PartialEq + Copy + fmt::Display> Head<T> {
    // 构建
    pub fn build() -> Self {
        Head { head: None }
    }
    // 搜索
    pub fn list_search(&mut self, k: T) -> Option<Rc<RefCell<DoubleLinkedList<T>>>> {
        let mut now = self.head.clone();
        while let Some(x) = now.clone() {
            let temp = Rc::clone(&x).as_ref().borrow().key;
            if temp != k {
                now = Rc::clone(&x).as_ref().borrow().next.clone();
            } else {
                break;
            }
        }
        now
    }
    // 插入（未排序）
    pub fn list_insert(&mut self, x: DoubleLinkedList<T>) {
        let mut x = x;
        x.next = self.head.clone();
        let x = Rc::new(RefCell::new(x));
        if let Some(l) = self.head.clone() {
            Rc::clone(&l).as_ref().borrow_mut().prev = Some(Rc::clone(&x));
        }
        self.head = Some(Rc::clone(&x));
    }
    // 删除
    pub fn list_delete(&mut self, x: DoubleLinkedList<T>) {
        if let Some(t) = x.prev.as_ref() {
            t.as_ref().borrow_mut().next = x.next.clone();
        } else {
            self.head = x.next.clone();
        }
        if let Some(t) = x.next.as_ref() {
            t.as_ref().borrow_mut().prev = x.prev;
        }
    }
}

// 3. 对象的分配与释放
#[derive(Debug)]
pub struct ArrayObject<T: PartialEq + Copy + fmt::Display> {
    next: Vec<Option<usize>>,
    key: Vec<T>,
    prev: Vec<Option<usize>>,
    l: Option<usize>,
    free: Option<usize>,
}
impl<T: PartialEq + Copy + fmt::Display> fmt::Display for ArrayObject<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "FREE: {:?}\n", self.free).unwrap();
        write!(f, "L   : {:?}\n", self.l).unwrap();
        let n = self.next.len();
        write!(f, "Next: ").unwrap();
        for i in 0..n {
            if let Some(i) = self.next[i] {
                write!(f, "{:4} -> ", i).unwrap();
            } else {
                write!(f, "Null -> ").unwrap();
            }
        }
        write!(f, "Over\n").unwrap();
        write!(f, "Key : ").unwrap();
        for i in 0..(self.key.len()) {
            write!(f, "{:4} -> ", self.key[i]).unwrap();
        }
        write!(f, "Over\n").unwrap();
        write!(f, "Prev: ").unwrap();
        for i in 0..n {
            if let Some(i) = self.prev[i] {
                write!(f, "{:4} -> ", i).unwrap();
            } else {
                write!(f, "Null -> ").unwrap();
            }
        }
        write!(f, "Over\n")
    }
}
impl<T: PartialEq + Copy + fmt::Display> ArrayObject<T> {
    pub fn build(n: usize) -> Self {
        let mut next = vec![Some(0 as usize); n];
        for i in 0..(n - 1) {
            next[i] = Some(i + 1);
        }
        next[n - 1] = None;
        let key: Vec<T> = Vec::<T>::with_capacity(n);
        let prev: Vec<Option<usize>> = vec![None; n];
        ArrayObject {
            next: next,
            key: key,
            prev: prev,
            l: None,
            free: Some(0),
        }
    }
    pub fn allocate_object(&mut self, x: T) {
        if let Some(i) = self.free {
            if let Some(j) = self.l {
                self.next[j] = Some(i);
                if let Some(v) = self.key.get_mut(i) {
                    *v = x;
                } else {
                    self.key.push(x);
                }
                self.prev[i] = Some(j);
                self.l = Some(i);
                self.free = self.next[i];
                self.next[i] = None;
            } else {
                self.key.push(x);
                self.l = Some(0);
                self.free = self.next[0];
                self.next[0] = None;
            }
        } else {
            panic!("out of space");
        }
    }
    pub fn free_object(&mut self, x: T) {
        let mut id = self.l;
        while let Some(i) = id {
            if self.key[i] == x {
                if let Some(j) = self.prev[i] {
                    self.next[j] = self.next[i];
                }
                if let Some(j) = self.next[i] {
                    self.prev[j] = self.prev[i];
                }
                self.next[i] = self.free;
                self.prev[i] = None;
                self.free = Some(i);
                id = None;
            } else {
                id = self.prev[i];
            }
        }
    }
}
